package algorithmic_data_structure.单调栈;

import utils.PrintUtil;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个数组，返回每个元素比他小且距离最接近的两个元素
 */
public class 找出离当前元素最接近的两个数 {
    @Test
    public void test(){
        PrintUtil.printArray(getNearLessRepeat(new int[]{0,2,1}));
    }
    public static int[][] getNearLessRepeat(int[] arr) {
        if (arr == null || arr.length == 0){
            return null;
        }
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int index = 0; index < arr.length; index++) {
            while (!stack.isEmpty() && arr[index] < arr[stack.peek().get(0)]){
                List<Integer> popList = stack.pop();
                for (Integer popIndex : popList) {
                    int rightNearest = index;
                    int leftNearest = stack.isEmpty() ? -1 : stack.peek().get(0);
                    res[popIndex][0] = leftNearest;
                    res[popIndex][1] = rightNearest;
                }
            }
            if (!stack.isEmpty() && stack.peek().get(0) == index){
                stack.peek().add(index);
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(index);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()){
            List<Integer> popList = stack.pop();
            for (Integer popIndex : popList) {
                int rightNearest = -1;
                int leftNearest = stack.isEmpty() ? -1 : stack.peek().get(0);
                res[popIndex][0] = leftNearest;
                res[popIndex][1] = rightNearest;
            }
        }
        return res;
    }

        //无重复元素
    public static int[][] getNearLessNoRepeat(int[] arr) {
        if (arr == null || arr.length == 0){
            return null;
        }
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int index = 1; index < arr.length; index++) {
            while (!stack.isEmpty() && arr[index] < arr[stack.peek()]){
                Integer pop = stack.pop();
                //右边最接近的元素就是使它出栈的元素下标
                int rightNearest = index;
                //左边最接近的元素就是他压着的那个元素，如果stack为空说明左边没有比他小的元素
                int leftNearest = stack.isEmpty() ? -1 : stack.peek();
                res[pop][0] = leftNearest;
                res[pop][1] = rightNearest;
            }
            stack.push(index);
        }
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            int rightNearest = -1;
            int leftNearest = stack.isEmpty() ? -1 : stack.peek();
            res[pop][0] = leftNearest;
            res[pop][1] = rightNearest;
        }
        return res;
    }
}
